﻿#define _CRT_SECURE_NO_WARNINGS
#include"tree.h"
#include"ZY0929_3.h"
// 二叉树前序遍历 
void BTPrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	BTPrevOrder(root->left);
	BTPrevOrder(root->right);
}
// 二叉树中序遍历
void BTInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BTInOrder(root->left);
	printf("%c ", root->data);
	BTInOrder(root->right);
}
// 二叉树后序遍历
void BTPostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BTPostOrder(root->left);
	BTPostOrder(root->right);
	printf("%c ", root->data);
}
// 二叉树节点个数
int BTSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BTSize(root->left) + BTSize(root->right);
}
// 二叉树叶子节点个数
int BTLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BTLeafSize(root->left) + BTLeafSize(root->right);
}
// 二叉树第k层节点个数
int BTLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
		return 1;
	return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k - 1);
}
//⼆叉树的深度/⾼度
int BTDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = BTDepth(root->left);
	int right = BTDepth(root->right);
	return 1 + (left > right ? left : right);
}

// 二叉树查找值为x的节点
BTNode* BTFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BTFind(root->left,x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BTFind(root->right,x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}
// 二叉树销毁
void BTDestory(BTNode** root)
{
	if (*root == NULL)
		return;
	BTDestory(&((*root)->left));
	BTDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

// 层序遍历(这里要用到队列的结构)，把结点元素放入队列中，然后取队顶元素打印，再删除队顶元素
void BTLevelOrder(BTNode* root)
{
	if (root == NULL)
		return;
	Queue Q;
	QueueInit(&Q);
	QueuePush(&Q, root);
	while (!QueueEmpty(&Q))
	{
		BTNode* top = QueueFront(&Q);
		printf("%c ", top->data);
		QueuePop(&Q);
		if(top->left)
			QueuePush(&Q, top->left);
		if (top->right)
			QueuePush(&Q, top->right);
	}
	QueueDestroy(&Q);
}



// 判断⼆叉树是否是完全⼆叉树
//逻辑很简单，其实就是同上面的层级遍历，先把结点放入队列之中，然后取队头，如果队头
// 不为空，则出队头，把结点左右的结点都放进去，这里的NULL也放进去，为空则结束循环，
// 循环判断队列中是否全为空，只要有一个非空，则为不完全二叉树，反之相反。
bool BTComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q,root);
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
